package 算法.其他算法;

import java.util.HashSet;

/**
 * 输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
 */
public class JZ43整数中1出现的次数_从1到n整数中1出现的次数 {

    //按位统计法  先求个位上的1  再求十位  百位
    /**
     *  几个变量公式 ： cur = (n/bit)%10   low = n%bit   high = n /bit / 10
     *  几种情况：
     *      cur > 1  ==> (high + 1) * bit
     *      cur = 1  ==> (high * bit ) + (1+ low)
     *      cur =0   ==> high * bit
     *
     *      5 0 1 [2] 2 2   ==》  0-501   0-99  ==> hgih+1   *   bit
     *      5 0 [1] 2 2 2   ==>  0-49    0-999    50     0-222  ===>  (high * bit) + (low + 1)
     *      5 [0] 1 2 2 2   ==>  0-4     0-9999     ===>  high * bit
     * */
    public int NumberOf1Between1AndN_Solution4(int n) {
        long bit = 1;
        long sum = 0;
        while (bit<=n){
            long cur = (n/bit)%10;
            long low = n % bit;
            long high = n / bit / 10;
            if(cur>1)
                sum += (high+1) * bit;
            else if(cur==1)
                sum += (high*bit) + (1+low);
            else
                sum += high * bit;
            bit *= 10;
        }
        return  (int)sum;
    }
    public int NumberOf1Between1AndN_Solution3(int n) {
        int res = 0;
        //MulBase = 10^i
        long MulBase = 1;
        //每位数按照公式计算
        for(int i = 0; MulBase <= n; i++){
            //根据公式添加
            res += (n / (MulBase * 10)) * MulBase + Math.min(Math.max(n % (MulBase * 10) - MulBase + 1, (long)0), MulBase);
            //扩大一位数
            MulBase *= 10;
        }
        return res;
    }



    //暴力统计法
    public int NumberOf1Between1AndN_Solution(int n) {
        int cnt = 0;
        for(int i=1;i<=n;i++){
            String num = "" + i;
            for(int j=0;j<num.length();j++)
                if(num.charAt(j)=='1')
                    cnt++;
        }
        return cnt;
    }

    //暴力统计法
    public int NumberOf1Between1AndN_Solution2(int n) {
        int res = 0;
        //遍历1-n
        for(int i = 1; i <= n; i++){
            //遍历每个数的每一位
            for(int j = i; j > 0; j = j / 10){
                //遇到数字1计数
                if(j % 10 == 1)
                    res++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new JZ43整数中1出现的次数_从1到n整数中1出现的次数().NumberOf1Between1AndN_Solution(1));
    }
}
